/**
 *  找出数组中重复的数字
 *      在一个长度为n的数组nums里的所有数组都在0~n-1的范围内 数组中某些数字是重复的, 但不知道有几个数字重复了,
 *        也不知道每个数字重复了几次, 请找出数组中任意一个重复的数字
 * */
const Solution = function (nums) {
    for (let i = 0; i < nums.length; i++) {
        while (nums[i] != i) {
            if (nums[nums[i]] == nums[i]) {
                return nums[i]
            }
            let temp = nums[i]
            nums[i] = nums[nums[i]]
            nums[temp] = temp
        }
    }
    return -1
}
console.log(Solution([2, 3, 1, 0, 2, 5, 3]))
/**
 *二维数组的查找
 *  在一个 n*m的二维数组中, 每一行都按照从左到右递增的顺序排序, 每一列都按照从上到下递增的顺序排序 请完成一个高效的函数,输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
 *      从右上角开始查找法或行列递增查找法
 *          1.从右上角的元素 设置两个指针i和j 分别指向行和列
 *          2.如果当前元素等于target, 则直接返回true
 *          3.如果当前元素大于target, 由于该数组的每一行和每一列都是递增的, 因此可以将列指针j左移一位, 缩小范围
 *          4.如果当前元素小于target,不断重复2,3,4 知道找到目标元素或者遍历完整个数组
 * */
const findNumberIn2DArray = function (matrix, target) {
    let m = matrix.length;
    if (m == 0) return false
    let n = matrix[0].length
    let i = 0, j = n - 1
    while (i < m && i >= 0 && j < n && j >= 0) {
        if (matrix[i][j] == target) {
            return true
        }
        if (matrix[i][j] > target) {
            j = j - 1
        } else {
            i = i + 1
        }
    }
    return false
}
console.log('findNumberIn2DArray:', findNumberIn2DArray([
    [1, 4, 7, 11, 15],
    [2, 5, 8, 12, 19],
    [3, 6, 9, 16, 22],
    [10, 13, 14, 17, 24],
    [18, 21, 23, 26, 30]
], 5))

/**
 * 替换空格 实现一个函数吧字符串s中每个空格都替换成"%20"
 * */
const replaceSpace = function (s) {
    return s.replace(/ /g, '%20');
}
console.log(replaceSpace('We are happy.'))

/**
 * 从头到尾打印链表
 *      输入head = [1,3,2]
 *      输出 [2,3,1]
 * */
// 创建链表节点
class LinkedNode {
    constructor(val, next = null) {
        this.val = val
        this.next = next
    }
}

// 创建链表
class LinkedList {
    constructor() {
        this.size = 0
        this.head = null
    }

    append(data) {
        let linkedNode = new LinkedNode(data)
        if (this.head == null) {
            this.head = linkedNode
        } else {
            let curNode = this.head
            while (curNode.next !== null) {
                curNode = curNode.next
            }
            curNode.next = linkedNode
        }
        this.size++
    }
}

const linkedList = new LinkedList()
linkedList.append(1)
linkedList.append(3)
linkedList.append(2)
console.log(linkedList)
// 从尾到头打印链表,输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
const reversePrint = function (linkedList) {
    let rst = []
    let head = linkedList.head
    while (head != null) {
        rst.unshift(head.val)
        head = head.next
    }
    return rst
}
console.log('reversePrint: ', reversePrint(linkedList))

/**
 * 重建二叉树
 *      输入某二叉树的前序遍历和中序遍历的结果, 请构建二叉树并返回其根节点
 *      假设输入的前序遍历和中序遍历的结果中都不包含重复的数字
 *          前序遍历: 根左右, 前序遍历: 第一个元素总是当前子树的根节点
 *          中序遍历: 左根右, 后序遍历根节点将左右两棵子树分开
 *          后序遍历: 左右根
 *  前序遍历: preorder = [3,9,20,15,7], 中序遍历: inorder = [9,3,15,20,7]
 *  期望: [3,9,20,null, null 15, 7]
 * */
// 创建树节点
class TreeNode {
    constructor(key, left = null, right = null) {
        this.key = key
        this.left = left
        this.right = right
    }
}

// 创建二叉树
class BinarySearchTree {
    constructor() {
        this.root = null
    }

    insert(key) {
        let newNode = new TreeNode(key)
        if (this.root == null) {
            this.root = newNode
        } else {
            this.insertNode(this.root, newNode)
        }
    }

    insertNode(root, node) {
        if (node.key < root.key) {
            // 左子树
            if (root.left == null) {
                root.left = node
            } else {
                this.insertNode(root.left, node)
            }
        } else {
            if (root.right == null) {
                root.right = node
            } else {
                this.insertNode(root.right, node)
            }
        }
    }
}

const buildTee = function (preorder, inorder) {
    if (preorder.length == 0 || inorder.length == 0) {
        return null
    }
    const rootVal = preorder[0]
    const root = new TreeNode(rootVal)
    const mid = inorder.indexOf(rootVal)
    const inorderLeft = inorder.slice(0, mid)
    const inorderRight = inorder.slice(mid + 1)
    const preorderLeft = preorder.slice(1, 1 + inorderLeft.length)
    const preorderRight = preorder.slice(1 + inorderLeft.length)
    root.left = buildTee(preorderLeft, inorderLeft)
    root.right = buildTee(preorderRight, inorderRight)
    return root
}
console.log(buildTee([3, 9, 20, 15, 7], [9, 3, 15, 20, 7]))

/**
 * 用两个栈实现队列
 *    用两个栈 实现一个队列, 队列的声明如下, 请实现它的两个函数 appendTail和 deleteHead, 分别完成在队列尾部插入整数
 *     和在队列头部删除整数的功能 (若队列中没有元素, deletehead操作返回 -1)
 *   输入：
 *    ["CQueue","appendTail","deleteHead","deleteHead"]
 *    [[],[3],[],[]]
 *    输出：[null,null,3,-1]
 * */

class CQueue {
    constructor() {
        this.s1 = []
        this.s2 = []
    }

    appendTail(value) {
        this.s1.push(value)
    }

    deleteHead() {
        if (this.s2.length == 0) {
            while (this.s1.length !== 0) {
                this.s2.push(this.s1.pop())
            }
        }
        if (this.s2.length == 0) {
            return -1
        }
        return this.s2.pop()
    }

}

const cQueue = new CQueue()
cQueue.appendTail(3); // 入队 3
console.log(cQueue.deleteHead())
console.log(cQueue.deleteHead())

/**
 * 斐波那契数列
 *      写一个函数, 输入 n, 求斐波那契数列的第n项, 斐波那契数量的定义如下: F0=0, F1= 1 Fn = F(n-1) + F(N-1)
 * */
const fibonacci = function (n) {
    if (n == 0) {
        return [1]
    }
    if (n == 1) {
        return [1, 1]
    }
    const fibonacciList = [1, 1]

    for (let i = 2; i < n; i++) {
        fibonacciList.push(fibonacciList[i - 1] + fibonacciList[i - 2])
    }
    return fibonacciList
}
console.log("fibonacci:" + fibonacci(6))

/**
 * 青蛙跳台阶问题: 一只青蛙一次可以跳上一级台阶 也可以跳上n级的台阶, 总共有多少种跳法
 * 1->[1]
 * 2->[1,1], [2]
 * 3->[1],剩2,[1,1],[2]
 * */
const jumpFloor = function (n) {
    if (n == 1) {
        return 1
    } else if (n == 2) {
        return 2
    } else {
        return jumpFloor(n - 1) + jumpFloor(n - 2)
    }
}
console.log('jumpFloor:', jumpFloor(3))
console.log('jumpFloor:', jumpFloor(5))

/**
 * 旋转数组的最小数字
 *      把一个数组最开始的若干个元素搬到数组的末尾, 我们称之为数组的旋转, 输入一个递增排序的数组的一个旋转, 输出旋转数组的最小元素
 *
 * */
const rorateArrMin = function (list) {
    // if (list.length == 0) return -1
    // if (list.length == 1) return list[0]
    // for (let i = 0; i < list.length; i++) {
    //     if (list[i + 1] < list[i]) {
    //         return list[i + 1]
    //     }
    // }
    // return list[0]
    let n = list.length
    let r = n - 1
    if (list[r] > list[0]) {
        return list[0]
    }
    while (r >= 0 && list[r] == list[0]) {
        r--
    }
    if (r == -1) {
        return list[0]
    }
    if (list[r] > list[0]) {
        return list[0]
    }
    let l = 0
    while (l < r) {
        let mid = l + r >> 1
        if (list[mid] < list[0]) {
            r = mid
        } else {
            l = mid + 1
        }
    }
    return list[r]
}
console.log('rorateArrMin:', rorateArrMin([3, 4, 5, 1, 2]))
console.log('rorateArrMin:', rorateArrMin([2, 2, 2, 0, 1]))
console.log('rorateArrMin:', rorateArrMin([2, 2, 2]))

/**
 *给定一个m*n二维字符网格board和一个字符串单词word 如果word存在于网格中 返回true, 否则返回false
 *  单词必须按照字母顺序 通过相邻的单元格内的字母构成 其中响铃单元格是那些水平相邻或垂直相邻的单元格, 同一个单元格内的字母不允许被重复使用
 * */

const exist = function (board, word) {

}

/**
 * 地上有一个m行n列的方格,从坐标[0,0] 到坐标[m-1, n-1] 一个机器人从坐标[0,0] 的格子开始运动, 他每次可以向左,右,上,下移动一格
 * 不能移动到方格外, 也不能进入行坐标和列坐标的数位之和大于K的格子, 例如当K未18时, 机器人能够进入方格[35,37], 因为3+5+3+7=18
 * 但他不能进入[35,38] 因为3+5+3+8=19, 请问该机器人能够到达多少个格子
 * */
const movingCount = function (m, n, k) {
    let visited = Array.from({length: m}, () => Array(n).fill(false))

    function getDigitSum(num) {
        let sum = 0
        while (num > 0) {
            sum += num % 10
            num = Math.floor(num / 10)
        }
        return sum
    }

    function dfs(i, j) {
        if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || getDigitSum(i) + getDigitSum(j) > k) {
            return 0
        }
        visited[i][j] = true
        return 1 + dfs(i + 1, j) + dfs(i - 1, j) + dfs(i, j - 1)
    }

    return dfs(0, 0)
}
console.log('movingCount:', movingCount(3, 3, 2))

/**
 * 剪绳子破镜重圆我只相信存在于小说里“我还记得你的好”，就是我能给你最好的告别。 ​​​
 *      给你一根长度为n的绳子,请把绳子剪成整数长度的m段,每段绳子的长度记为k[0], k[1]...k[m-1],请问
 *          k[0]*k[1]*...*k[m-1]可能的最大乘积是多少, 例如当绳子的长度为 8时, 我们把他剪成分别为2,3,3的三段,此时得到的最大乘积是18。
 * */
const cuttingRope = function (n) {
    if (n <= 3) {
        return n - 1
    }

    const mod = n % 3;
    const cnt = Math.floor(n / 3)

    if (mod === 1) {
        return Math.pow(3, cnt - 1) * 4
    } else if (mod === 0) {
        return Math.pow(3, cnt)
    } else {
        return Math.pow(3, cnt) * mod
    }
}
console.log('cuttingRope:', cuttingRope(8))

/**
 * 二进制中1的个数
 *  编写一个函数, 输入是一个无符号整数(以二进制的形式), 返回其二进制表达式中数字位数为'1'的个数(也被称为汉明重量)
 * */
const hammingWeight = function (n) {
    let ans = 0
    while (n != 0) {
        // 位运算 操作的不是整数本身 而是整数的二进制数
        // 11001 11000  11000
        // 11000 10111  10000
        // 10000 01111  00000
        n = n & (n - 1)
        ans++
    }
    return ans
}

function decimalToBinary(num) {
    if (num === 0) {
        return '0';
    }

    let stack = [];
    while (num > 0) {
        const remainder = num % 2;
        stack.push(remainder);
        num = Math.floor(num / 2);
    }

    let binaryString = '';
    while (stack.length > 0) {
        binaryString += stack.pop().toString();
    }
    return binaryString;
}

console.log("hammingWight: ", hammingWeight(25))

/**
 *  打印从1到最大的n位数
 *      输入数字n 按顺序打印出从1到最大的n位十进制数, 比如输入3, 则打印出1,2,3一直到最大的3位数999
 * */
const printNumber = function (n) {
    let rst = []
    for (let i = 1; i <= (Math.pow(10, n) - 1); i++) {
        rst.push(i)
    }
    return rst
}
console.log("printNumber: ", printNumber(1))
/**
 * 给单向链表的头指针和一个要删除的节点的值, 定义一个函数删除该节点 返回删除后的链表的头节点
 * */

const deleteLinkListNode = function (head, value) {
    // 如果头节点就是要删除的节点
    while (head && head.value === value) {
        head = head.next
    }

    let current = head
    while (current && current.next) {
        if (current.next.value === value) {
            current.next = current.next.next
        } else {
            current = current.next
        }
    }

    return head
}

/**
 * 调整数组顺序使奇数位于偶数前面
 *  输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数在数组的前半部分, 所有的偶数在数组的后半部分
 * */
const exchange = function (list) {
    let l = 0
    let r = list.length - 1
    while (l < r) {
        while (l < r && list[l] % 2 == 1) {
            l++
        }
        while (l < r && list[r] % 2 == 0) {
            r--
        }
        if (l < r) {
            let temp = list[l]
            list[l] = list[r]
            list[r] = temp
        }
    }
    return list
}
console.log("exchange: ", exchange([1, 2, 3, 4, 5, 6, 7, 8, 9]))

/**
 * 链表中倒数第K个节点
 *      一个链表有6个节点,从头节点开始他们的值一次是1,2,3,4,5,6 这个链表的倒数第三个节点值位4的节点
 * */

const kth_linkList = new LinkedList()
kth_linkList.append(1)
kth_linkList.append(2)
kth_linkList.append(3)
kth_linkList.append(4)
kth_linkList.append(5)
kth_linkList.append(6)

const getKthFormEnd = function (head, k) {
    let slow = head
    let fast = head
    for (let i = 0; i < k; i++) {
        fast = fast.next;
    }
    while (fast != null) {
        fast = fast.next
        slow = slow.next
    }
    return slow.val
}
console.log("getKthFormEnd: ", getKthFormEnd(kth_linkList.head, 3))

/**
 * 翻转链表
 *     定义一个函数. 输入一个链表的头节点 翻转并输出后链表的头节点
 * */
console.log(JSON.stringify(kth_linkList))

const reverseList = function (head) {
    if (head == null) return null
    if (head.next == null) return head
    let prev = null
    let curr = head
    while (curr != null) {
        let nextNode = curr.next
        curr.next = prev
        prev = curr
        curr = nextNode
    }
    return prev
}
console.log("reverseList: ", JSON.stringify(reverseList(kth_linkList.head)))

/**
 * 合并两个排序的链表
 *     输入两个递增排序的链表, 合并这两个链表并使新链表的节点仍然是递增排序的
 *  示例1:
 *      输入: 1->2->4, 1->3->4
 *      输出: 1->1->2->3->4->4
 * */
const mergeTwoLists = function (l1, l2) {
    if (l1 == null) {
        return l2
    }
    if (l2 == null) {
        return l1
    }
    let merged = null
    if (l1.val < l2.val) {
        merged = l1
        merged.next = mergeTwoLists(l1.next, l2)
    } else {
        merged = l2
        merged.next = mergeTwoLists(l1, l2.next)
    }
    return merged
}
let head1 = new LinkedList()
head1.append(1)
head1.append(2)
head1.append(4)
let head2 = new LinkedList()
head2.append(1)
head2.append(3)
head2.append(4)
console.log("mergeTwoLists: ", mergeTwoLists(head1.head, head2.head))

/**
 * 从上到下打印二叉树
 *      从上到下打印出二叉树的每一个节点, 同一层的节点按照从做到右的顺序打印
 * */
const binarySearchTree = new BinarySearchTree()
binarySearchTree.insert(3)
binarySearchTree.insert(2)
binarySearchTree.insert(1)
binarySearchTree.insert(4)
binarySearchTree.insert(5)
console.log(JSON.stringify(binarySearchTree))

const levelOrder = function (root) {
    // 采用广度优先遍历的方法遍历二叉树
    if (root == null) return null
    // 存放结果数组
    let ans = []
    // 创建队列
    let queue = []
    // 将二叉树放入队列中
    queue.push(root)
    // 不断的将对头元素放入队列中

    while (queue.length > 0) {
        let size = queue.length

        for (let i = 0; i < size; i++) {
            let node = queue.shift()
            ans.push(node.key)

            if (node.left != null) {
                queue.push(node.left)
            }
            if (node.right != null) {
                queue.push(node.right)
            }
        }
    }

    // 返回结果
    return ans
}
console.log("levelOrder: ", levelOrder(binarySearchTree.root))

/**
 * 从上到下打印二叉树II
 *   从上到下按层打印二叉树, 同一层的节点从左到右的顺序打印, 每一层打印到一行
 * */

/**
 *  最小的K个数
 *      输入整数数组arr, 找出其中最小的K个数, 例如输入4,5,1,6,2,7,3,8这八个数字, 则最小的四个数字是1,2,3,4
 * */
const getLeastNumbers = function (list, k) {
    // k必须为正整数
    if (k > list.length || list.length == 0 || k <= 0) return []
    return list.sort((a, b) => a - b).slice(0, 4)
}
console.log("getLeastNumbers: ", getLeastNumbers([4, 5, 1, 6, 2, 7, 3, 8], 4))

/**
 * 输入一个整型数组, 数组中的一个或连续多个整数组成一个子数组, 求所有子数组的和的最大值 要求时间复杂度为O(n)。
 归并排序Q的核心思想就是“分治”，在本题中我们依然可以借助这种“分而治之”的思想。“分治法”的主要思想就是将大问题分解为若干个小问题，
 然后将各个小问题各个击破，然后再将各个子问题合并即可得到原问题的解，其实这和递归的思想有些相似，
 因此“分治法Q”一般和递归是分不开的。具体到本题而言就是利用数组的“中点”将原数组分解为左右两个小数组，
 分别计算出左右两个子数组中的连续子数组最大和，然后将左右两个数组合并得到包含所选中点的连续数组的最大和
 ，最后再选出左右连续数组最大和、合并后包含中点连续数组最大和三者中的最大值即可然后分别对左右两个小数组执行以上过程即能得到正确结果。
 * */

const maxSubArray = function (arr) {
    if (arr.length === 0) return 0
    let sum = 0, ans = arr[0]
    for (let i = 0; i < arr.length; i++) {
        if (sum >= 0) {
            sum += arr[i]
        } else {
            sum = arr[i]
        }
        ans = Math.max(ans, sum)
    }
    return ans
}
console.log("maxSubArray:", maxSubArray([-1, 2, -1, 1, -4, 5]))

const maxSum = function (arr, left, right) {
    // 结束递归的条件
    if (left == right) return arr[left]
    let mid = left + ((right - left) >> 1)
    let leftMaxSum = maxSum(arr, left, mid)
    let rightMaxSum = maxSum(arr, mid + 1, right)
    // 计算从中点向左连续数组的最大和
    let leftBorderSum = 0, leftMaxBorderSum = arr[mid]
    for (let i = mid; i >= left; i--) {
        leftBorderSum = arr[i]
        if (leftBorderSum > leftMaxBorderSum) {
            leftMaxBorderSum = leftMaxSum
        }
    }
    // 计算从中点向右连续数组的最大和
    let rightBorderSum = 0, rightMaxBorderSum = arr[mid]
    for (let i = mid; i <= right; i++) {
        rightBorderSum = arr[i]
        if (rightBorderSum > rightMaxBorderSum) {
            rightBorderSum = rightMaxBorderSum
        }
    }
    return Math.max(Math.max(leftMaxSum, rightMaxSum), leftMaxBorderSum + rightMaxBorderSum)
}
const max_sub_arr = function (arr) {
    return maxSum(arr, 0, arr.length - 1)
}
console.log("max_sub_arr: ", max_sub_arr([-1, 2, -1, 1, -4, 5]))

/** 1~n整数中1 出现的次数, 输入一个整数n, 求1~n这n个整数的十进制表示中1出现的次数
 * 将1~n的个位, 十位, 百位的1出现的次数相加, 即为1出现的总次数
 *      以n=1234567为例,需要统计[百位]上数字1出现的次数, 对于从0开始每1000个数, 百位上的数字1都会出现100次, 即数的最后三位每1000
 *      个数都呈现[000, 999]的循环, 其中[100,199]在百位上的数字1, 共有100个
 *      n拥有1234个这样的循环, 每个循环[百位]位上都出现了100次1, 这样就一共出现了1234*100次1
 *
 * */
const countDigitOne = function (n) {
    let ans = 0
    let range = 1
    let l = Math.floor(n / 10)
    let cur = n % 10
    let r = 0
    while (!(l == 0 && cur == 0)) {
        if (cur == 0) {
            ans += l * range
        } else if (cur == 1) {
            ans += l + range + r + 1
        } else {
            ans += (l + 1) * range
        }
        r += cur * range
        cur = l % 10
        l = Math.floor(l / 10)
        range *= 10
    }
    return ans
}
console.log("countDigitOne: ", countDigitOne(12))

/**
 *数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。
 * */
const findNthDigit = function (n) {
    if (n < 10) return n

}

/**
 *  把数组排成最小的数
 *      输入一个非负整数数组, 把数组里所有数组拼接起来拍成一个数, 打印能拼接处的所有数字中最小的一个
 *      输入[10,2]
 *      输出 '102'
 * */
const minNumber = function (arr) {
    if (arr.length == 0) return ''
    let strs = []
    for (let i = 0, len = arr.length; i < len; i++) {
        strs.push(String(arr[i]))
    }
    strs.sort((a, b) => (a + b) - (b + a))
    console.log(strs)
    let ans = ''
    for (let i = 0; i < strs.length; i++) {
        ans += strs[i]
    }
    return ans
}
console.log("minNumber:",minNumber([10, 2]))
console.log("minNumber:",minNumber([3,30,34,5,9]))


const data = [
    {
        id: 1,
        title: "课程 1",
        children: [
            {id: 4, title: '课程1-1'},
            {
                id: 5,
                title: '课程1-2',
                children: [
                    {id: 6, title: '课程 1-2-1 '}, {id: 7, title: "课程 1-2-2"},
                ]
            }
        ]
    },
    {id: 2, title: "课程 2"},
    {id: 3, title: "课程 3"},
]

function flaten(data, res) {
    if (data.length == 0) return res
    for (let i = 0; i < data.length; i++) {
        res.push({id: data[i].id, title: data[i].title})
        if (Array.isArray(data[i].children)) {
            res.concat(flaten(data[i].children, res))
        }
    }
    return res
}

function flattenDepthFirst(data, arr = []) {
    let res = arr || [];
    data.forEach(item => {
        let { children, ...attr } = item;
        res.push(attr);

        if (children && children.length) {
            // 递归将所有节点加入到结果集中
            flattenDepthFirst(children, res);
        }
    });
    return res;

}

console.log(flaten(data, []))
console.log(flattenDepthFirst(data, []))
